import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author 03010570
 * @date 2020/07/16
 * describe:    LeetCode : 763、划分字母区间    https://leetcode-cn.com/problems/partition-labels/
 */
public class LeetCode_763 {

    public static void main(String[] args) {
        List<Integer> list = partitionLabels("ababcbacadefegdehijhklij");
        for (Integer integer : list) {
            System.out.println(integer);
        }
    }

    /**
     * 时间复杂度 : O(N) 遍历两次 字符串长度
     * 空间复杂度 : O(1) 固定长度为 26 的数组
     * 思路： 贪心 + 双指针
     * 1、因为每个字母都需要划分在同一个片段里，遍历 字符串 先找到每个字母对应的最后一个下标， str[26]
     * 2、原则： 单个字母的最后一个下标 一定 小于等于当前片段的下标
     * 小于的时候，说明没有找到当前片段的最后一个下标
     * 等于的时候，说明当前字母的最后一个下标就是当前片段的下标。
     *
     * @param S
     * @return
     */
    public static List<Integer> partitionLabels(String S) {
        int[] ints = new int[26];
        for (int i = 0; i < S.length(); i++) {
            ints[S.charAt(i) - 'a'] = i;
        }
        int start = 0, end = 0;
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < S.length(); i++) {
            end = Math.max(end, ints[S.charAt(i) - 'a']);
            if (i == end) {
                res.add(end - start + 1);
                start = end + 1;
            }
        }
        return res;


    }
}
